1. Field of the Invention
This invention relates to a correspondence-between-images detection method and system belonging to, for example, the following technical fields:
1. Image coder-decoder for knowing the correspondence between images consecutive in time sequence and transmitting and storing the images in a small coding amount.
2. Measuring device for finding the correspondence holding between stereoscopic images and measuring a distance.
3. Image processor for compensating motion of an image caused by unintended motion of a camera, such as camera shake.
4. Image processor for integrating a plurality of images into a wide-view image such as a panoramic image.
2. Description of the Related Art
As the viewpoint of a camera or an object moves, the object is projected at a different position in an image. The correspondence between the two projection images can be represented as mapping of a position set on one image to a position set on the other.
There are various models of mappings and the following are known as mappings from point to point: Two-dimensional affine mapping represented in expressions 1 to 3; two-dimensional quadratic form mapping represented in expressions 4 to 6; and planar perspective mapping represented in expressions 7 and 8.
They represent the correspondence between projection images produced by relative motion between an object and a camera sufficiently distant from each other, an instantaneous move of a plane, and an arbitrary move of a plane.
Here, (x, y) and (xxe2x80x2, yxe2x80x2) denote the corresponding image positions between different projection images, superscript letter t denotes transpose of a vector, a matrix, and solid letter x represents coordinates (x, y).
Two-dimensional affine mapping:
xxe2x80x2=Pa(x)axe2x80x83xe2x80x83(1)                                           P            a                    ⁡                      (            x            )                          =                  (                                                    x                                            y                                            1                                            0                                            0                                            0                                                                    0                                            0                                            0                                            x                                            y                                            1                                              )                                    (        2        )            
Parameters of two-dimensional affine mapping:
a=(a0,a1,a2,a3,a4,a5)xe2x80x2xe2x80x83xe2x80x83(3)
Two-dimensional quadratic form mapping:
xxe2x80x2=Pq(x)qxe2x80x83xe2x80x83(4)                                           P            q                    ⁡                      (            x            )                          =                  (                                                    x                                            y                                                              x                  2                                                            xy                                            1                                            0                                            0                                            0                                                                    0                                            0                                            xy                                                              y                  2                                                            0                                            x                                            y                                            1                                              )                                    (        5        )            
Parameters of two-dimensional quadratic form mapping:
q=(q0,q1,q2,q3,q4,q5,q6,q7)xe2x80x2(6)
Plane perspective mapping:                               x          xe2x80x2                =                              f            ⁡                          (                              x                ;                p                            )                                =                      (                                                                                                                                                        p                          0                                                ⁢                        x                                            +                                                                        p                          1                                                ⁢                        y                                            +                                              p                        2                                                                                                                                      p                          6                                                ⁢                        x                                            +                                                                        p                          7                                                ⁢                        y                                            +                      1                                                                                                                                                                                                                p                          3                                                ⁢                        x                                            +                                                                        p                          4                                                ⁢                        y                                            +                                              p                        5                                                                                                                                      p                          6                                                ⁢                        x                                            +                                                                        p                          7                                                ⁢                        y                                            +                      1                                                                                            )                                              (        7        )            
Parameters of plane perspective mapping:
p=(p0,p1,p2,p3,p4,p5,p6,p7)xe2x80x2xe2x80x83xe2x80x83(8)
If the parameters of each mapping are defined, a function of determining the positional correspondence between different images is defined. If the six parameters shown in expression 3 are found in the two-dimensional affine mapping, the correspondence between the images is described; if the eight parameters shown in expression 6 are found in the two-dimensional quadratic form mapping, the correspondence between the images is described; and if the eight parameters shown in expression 8 are found in the planar perspective mapping, the correspondence between the images is described.
The mapping representing the correspondence between the images is not limited to the point-to-point correspondence; a more general mapping from a position set on one image to a position set on the other is also possible. In the above-described point-to-point correspondence, there is a restriction (plane) on the projection condition and the structure of an object, but mapping generally holding between the different projection images of a rigid body is known as epipolar geometry. It is a mapping from a line to a line, called epipolar mapping in the specification. A mapping from a point to a line exists as generalization of the epipolar mapping. It is represented in expressions 9 and 10 and will be referred to as generalized epipolar mapping. Generalized epipolar mapping:                               Line,  1:                ⁢                  {                                                    x                xe2x80x2                            |                                                                    x                    xe2x80x2                                                        -                    t                                                  ⁢                F                ⁢                                  x                  ~                                                      =            0                    }                                    (        9        )            
F in expression 9 denotes a 3xc3x973 matrix called a fundamental matrix and symbol xcx9c denotes homogeneous coordinate representation shown in expression 10 (two-dimensional position coordinates are represented as a three-dimensional vector as (x, y, 1) rather than (x, y)). For the generalized epipolar mapping, xxe2x80x2 mapped from x satisfies an equation of a line represented by the matrix F. That is, a point is mapped to a line. The mapping parameter is the matrix F itself (a detailed description of the epipolar mapping will be again given in Embodiment).
To find the mapping parameters, hitherto, a method based on feature point correspondence or a method using direct minimization of an intensity error has been used. The planar perspective mapping is taken as an example.
Since the number of parameters to be found is eight in the planar perspective mapping, if four-point correspondence is obtained between different projection images, a function can be defined.
Eight simultaneous equations are obtained from expression 7 with respect to the four-point correspondence, whereby the mapping parameters can be calculated easily. The parameters of the two-dimensional affine mapping can be found from six simultaneous equations in the three-point correspondence and those of the two-dimensional quadratic form mapping can be found from eight simultaneous equations in the four-point correspondence.
{tilde over (x)}=(x,y,1)xe2x80x2, {tilde over (x)}xe2x80x2=(xxe2x80x2,yxe2x80x2,1)xe2x80x2,xe2x80x83xe2x80x83(10)
For the generalized epipolar mapping, a method based on eight-point correspondence by Longuet-Higgins is disclosed in document xe2x80x9cH. C. Longuet-Higgins, xe2x80x9cA computer algorithm for reconstructing a scene from two projections,xe2x80x9d Nature vol. 293, pp. 133-135, 1981.xe2x80x9d In the specification, such a method based on the feature point correspondence of projection images will be referred to as a parameter estimation method based on feature point correspondence.
The method of direct minimization of an intensity error is disclosed in, for example, xe2x80x9cR. Szeliski, xe2x80x9cVideo Mosaics for Virtual Environment,xe2x80x9d IEEE Computer Graphics and Applications, pp.22-30, March 1996.xe2x80x9d                    E        =                                            ∑              i                        ⁢                          xe2x80x83                        ⁢                                          [                                                                            I                      xe2x80x2                                        ⁡                                          (                                                                        x                          i                          xe2x80x2                                                ,                                                  y                          i                          xe2x80x2                                                                    )                                                        -                                      I                    ⁡                                          (                                                                        x                          i                                                ,                                                  y                          i                                                                    )                                                                      ]                            2                                =                                    ∑              i                        ⁢                          xe2x80x83                        ⁢                          e              i              2                                                          (        11        )            
This method is to minimize a intensity error defined in expression 11 with respect to the whole screen.
In expression 11, I (xi, yi) represents the intensity of the ith pixel and Ixe2x80x2 (xixe2x80x2, yixe2x80x2) denotes the intensity at the corresponding point of a different projection image.
Here, the planar perspective mapping defined in expression 7 is used as the mapping and the parameters of the planar perspective mapping are found. In the example in the related art, the intensity error is defined as a square error in expression 11, thus minimization of expression 11 is executed according to Levenberg-Marquart method. The details of the Levenberg-Marquart method are disclosed in xe2x80x9cW. H Press et al. xe2x80x9cNumerical Receipes in C: The art of Scientific Computing,xe2x80x9d Cambridge Univ. Press 1992.xe2x80x9d
In the example in the related art, the following steps are repeated for finding mapping parameter p:
Step 1: First, ei shown in expression 11 is calculated from an image.
Step 2: First-order partial differential of expression 11 is found according to expression 12.                                                        ∂                              e                i                                                    ∂                              p                0                                              =                                                    x                i                                            D                i                                      ⁢                          xe2x80x83                        ⁢                                          ∂                                  I                  xe2x80x2                                                            ∂                                  x                  xe2x80x2                                                                    ,        ⋯        ⁢                  xe2x80x83                ,                                            ∂                              e                i                                                    ∂                              p                7                                              =                      -                                                            y                  i                                                  D                  i                                            ⁢                              xe2x80x83                            [                                                                    x                    i                    xe2x80x2                                    ⁢                                      xe2x80x83                                    ⁢                                                            ∂                                              I                        xe2x80x2                                                                                    ∂                                              x                        xe2x80x2                                                                                            +                                                      y                    i                    xe2x80x2                                    ⁢                                      xe2x80x83                                    ⁢                                                            ∂                                              I                        xe2x80x2                                                                                    ∂                                              y                        xe2x80x2                                                                                                        ]                                                          (        12        )            
In expression 12, Di is a denominator of expression 11, namely, expression 13.
Di=p6xi+p7yi+1xe2x80x83xe2x80x83(13)
Step 3: Using expression 12, 8xc3x978 matrix A having element ak1 and column vector b having element bk are found as shown in expression 14.                                          a            k1                    =                                    ∑              i                        ⁢                          xe2x80x83                        ⁢                                                            ∂                                      e                    i                                                  ⁢                                  ∂                                      e                    i                                                                                                ∂                                      p                    k                                                  ⁢                                  ∂                                      p                    l                                                                                      ,                              b            k                    =                                    ∑              i                        ⁢                          xe2x80x83                        ⁢                                          ∂                                  e                  i                                                            ∂                                  p                  k                                                                                        (        14        )            
Step 4: Change of the mapping parameter, xcex4p, is calculated according to expression 15 and a new candidate of the mapping parameter, pxe2x80x2, is calculated according to expression 16. xcex is a non-negative control variable and the initial value of xcex is defined experimentally. I is a identity matrix.
xcex4p=(A+xcexI)xe2x88x921bxe2x80x83xe2x80x83(15)
pxe2x80x2=pxe2x88x92xcex4pxe2x80x83xe2x80x83(16)
Step 5: The value of expression 11 is calculated from pxe2x80x2 and if it is decreased as compared with the value calculated at step 1, p is replaced with pxe2x80x2 to update the mapping parameter. Further, in this case, the value of xcex is lessened. In contrast, if the value of expression 11 is decreased, the mapping parameter is not updated and the value of xcex is increased.
The Levenberg-Marquart method is known as a nonlinear iteractive minimization technique effective for parameter estimation for minimizing a square error. If expression 11 can be approximated as a quadratic function with respect to the mapping parameter, a Newton""s method can be used and the square error can be minimized based on the change of the mapping parameter, xcex4p, calculated in expression 17 as approximation of the Newton""s method (if the original Newton""s method is used, the matrix A is found as a second-order partial differential matrix).
xe2x80x83xcex4p=Axe2x88x921bxe2x80x83xe2x80x83(17)
However, in the nonlinear minimization, generally expression 11 often cannot be approximated as a quadratic function with respect to the mapping parameter. Then, as in expression 15, a identity matrix multiplied by xcex is added for executing stable convergence.
If the minimization step achieves success, the adjustment is made with xcex set to a small value so that the mapping parameter can be obtained in a small number of repetitions; if the minimization step ends in failure, the adjustment is made with xcex set to a large value so that more reliable convergence can be executed.
In view of the above, an object of the present invention is to eliminate the following problems.
Problem of the method based on feature point correspondence: If the feature points can be found accurately, the parameter estimation method based on feature point correspondence is straightforward and accurate. However, the correspondence between the positions where intensity patterns (features) resemble each other generally produces erroneous correspondence. It is difficult to determine whether or not the correspondence is erroneous correspondence. If the precision of the feature point correspondence is coarse, the precision of the obtained parameter also becomes coarse.
Problem of the method using direct minimization of an intensity error: In the method using direct minimization of an intensity error, if the coordinates of the correspondence positions on a screen differ largely, namely, if motion on the screen is large, parameter estimation is difficult to make.
To solve the above-described problems, according to a first aspect of the invention, there is provided a method of representing correspondence between two images as a function of mapping a position set on one image to a position set to the other and finding a mapping parameter for defining the function, thereby obtaining motion between the images, the method comprising (1a) error operation step of, for a plurality of local areas into which an image is divided, calculating the local area correspondence between two different images as an error and finding a displacement between the local areas reaching the minimum error and an error value in the proximity of the displacement, (1b) error function operation step of finding for each local area a quadratic error function with displacement as a variable from the displacement reaching the minimum error and the error value in the proximity of the displacement, and (1c) nonlinear iteractive minimization step of again representing the sum total or partial sum of the quadratic error functions in a parameter representing a function and executing nonlinear iteractive minimization for the parameter for finding a parameter, the nonlinear iteractive minimization step comprising (1c-1) partial differential operation step of finding a first-order partial differential vector and a second-order partial differential matrix concerning the parameter of the sum total or partial sum of the quadratic error functions, (1c-2) second-order partial differential matrix change step of increasing diagonal elements of the second-order partial differential matrix in response to the degree to which the minimization in each repetition falls below a predetermined expected value, and (1c-3) parameter change step of multiplying the first-order partial differential vector by an inverse matrix of the modified second-order partial differential matrix for providing a parameter increment or decrement, wherein each parameter increment or decrement provided by iterating the partial differential operation step, the second-order partial differential matrix change step, and the parameter change step is added sequentially for changing the parameter for executing the minimization.
In the specification, the first-order differential vector means a vector that consists of first order partial derivatives, and the second-order differential matrix means a matrix that consists of second order partial derivatives, e.g., Hessian matrix.
According to a second aspect of the invention, there is provided a system of representing correspondence between two images as a function of mapping a position set on one image to a position set to the other and finding a mapping parameter for defining the function, thereby obtaining motion between the images, the system comprising (2a) error operation means for, for a plurality of local areas into which an image is divided, calculating the local area correspondence between two different images as an error and finding a displacement between the local areas reaching the minimum error and an error value in the proximity of the displacement, (2b) error function operation means for finding for each local area a quadratic error function with displacement as a variable from the displacement reaching the minimum error and the error value in the proximity of the displacement, and (2c) nonlinear iteractive minimization means for again representing the sum total or partial sum of the quadratic error functions in a parameter representing a function and executing nonlinear iteractive minimization for the parameter for finding a parameter, the nonlinear iteractive minimization means comprising (2c-1) partial differential operation means for finding a first-order partial differential vector and a second-order partial differential matrix concerning the parameter of the sum total or partial sum of the quadratic error functions, (2c-2) second-order partial differential matrix change means for increasing diagonal elements of the second-order partial differential matrix in response to the degree to which the minimization in each repetition falls below a predetermined expected value, and (2c-3) parameter change means for multiplying the first-order partial differential vector by an inverse matrix of the modified second-order partial differential matrix for providing a parameter increment or decrement, wherein each parameter increment or decrement provided by iterating the partial differential operation means, the second-order partial differential matrix change means, and the parameter change means is added sequentially for changing the parameter for executing the minimization.
According to a third aspect of the invention, there is provided a method of representing correspondence between two images as a function of mapping a position set on one image to a position set to the other and finding a mapping parameter for defining the function, thereby obtaining motion between the images, the method comprising (3a) error operation step of, for a plurality of local areas into which an image is divided, calculating the local area correspondence between two different images as an error and finding a displacement between the local areas reaching the minimum error and an error value in the proximity of the displacement, (3b) error function operation step of finding for each local area a quadratic error function with displacement as a variable from the displacement reaching the minimum error and the error value in the proximity of the displacement, (3c) linear parameter operation step of again representing the sum total or partial sum of the quadratic error functions in a parameter representing a function, classifying into a linear-minimization-possible parameter with a partial derivative for parameter becoming a linear function and a nonlinear minimization parameter with a partial derivative for parameter not becoming a linear function, and finding only the former by executing linear minimization, and (3d) all parameter operation step of finding all parameters by executing nonlinear iteractive minimization of the sum total or partial sum of the quadratic error functions with the parameter found by executing the linear parameter operation step as an initial value for the linear-minimization-possible parameter.
According to a fourth aspect of the invention, there is provided a system of representing correspondence between two images as a function of mapping a position set on one image to a position set to the other and finding a mapping parameter for defining the function, thereby obtaining motion between the images, the system comprising (4a) error operation means for, for a plurality of local areas into which an image is divided, calculating the local area correspondence between two different images as an error and finding a displacement between the local areas reaching the minimum error and an error value in the proximity of the displacement, (4b) error function operation means for finding for each local area a quadratic error function with displacement as a variable from the displacement reaching the minimum error and the error value in the proximity of the displacement, (4c) linear parameter operation means for again representing the sum total or partial sum of the quadratic error functions in a parameter representing a function, classifying into a linear-minimization-possible parameter with a partial derivative for parameter becoming a linear function and a nonlinear minimization parameter with a partial derivative for parameter not becoming a linear function, and finding only the former by executing linear minimization, and (4d) all parameter operation means for finding all parameters by executing nonlinear iteractive minimization of the sum total or partial sum of the quadratic error functions with the parameter found by the linear parameter operation means as an initial value for the linear-minimization-possible parameter.
According to a fifth aspect of the invention, there is provided a method of representing correspondence between two images as a function of mapping a position set on one image to a position set to the other and finding a mapping parameter for defining the function, thereby obtaining motion between the images, the method comprising (5a) error operation step of, for a plurality of local areas into which an image is divided, calculating the local area correspondence between two different images as an error and finding a displacement between the local areas reaching the minimum error and an error value in the proximity of the displacement, (5b) error function operation step of finding for each local area a quadratic error function having a minimum value of zero with displacement as a variable from the displacement reaching the minimum error and the error value in the proximity of the displacement, (5c) recursive minimization step of again representing the weighted sum total of the quadratic error functions in a parameter representing a function and executing recursive minimization for the parameter for finding a parameter, and (5d) weighting resetting step of setting a weight indirectly proportional to the value of the quadratic error function in the iteration process of the recursive minimization.
According to a sixth aspect of the invention, there is provided a system of representing correspondence between two images as a function of mapping a position set on one image to a position set to the other and finding a mapping parameter for defining the function, thereby obtaining motion between the images, the system comprising (6a) error operation means for, for a plurality of local areas into which an image is divided, calculating the local area correspondence between two different images as an error and finding a displacement between the local areas reaching the minimum error and an error value in the proximity of the displacement, (6b) error function operation means for finding for each local area a quadratic error function having a minimum value of zero with displacement as a variable from the displacement reaching the minimum error and the error value in the proximity of the displacement, (6c) recursive minimization means for again representing the weighted sum total of the quadratic error functions in a parameter representing a function and executing recursive minimization for the parameter for finding a parameter, and (6d) weighting resetting means for setting a weight indirectly proportional to the value of the quadratic error function in the iteration process of the recursive minimization.
According to a seventh aspect of the invention, there is provided a method of representing correspondence between two images as a function of mapping a position set on one image to a position set to the other and finding a mapping parameter for defining the function, thereby obtaining motion between the images, the method comprising (7a) error operation step of, for a plurality of local areas into which an image is divided, calculating the local area correspondence between two different images as an error and finding a displacement between the local areas reaching the minimum error and an error value in the proximity of the displacement, (7b) error function operation step of finding for each local area a quadratic error function with displacement as a variable from the displacement reaching the minimum error and the error value in the proximity of the displacement, (7c) error parameter conversion step of again defining the sum total or partial sum of the quadratic error functions in a parameter for defining a function from the relationship between a line mapped and a displacement for determining the value of the quadratic error function, and (7d) minimization step of minimizing the sum total or partial sum of the quadratic error functions again converted into the parameter for parameter and outputting the minimization parameter as motion between the images.
According to an eighth aspect of the invention, there is provided a system of representing correspondence between two images as a function of mapping a position set on one image to a position set to the other and finding a mapping parameter for defining the function, thereby obtaining motion between the images, the system comprising (8a) error operation means for, for a plurality of local areas into which an image is divided, calculating the local area correspondence between two different images as an error and finding a displacement between the local areas reaching the minimum error and an error value in the proximity of the displacement, (8b) error function operation means for finding for each local area a quadratic error function with displacement as a variable from the displacement reaching the minimum error and the error value in the proximity of the displacement, (8c) error parameter conversion means for again defining the sum total or partial sum of the quadratic error functions in a parameter for defining a function from the relationship between a line mapped and a displacement for determining the value of the quadratic error function, and (8d) minimization means for minimizing the sum total or partial sum of the quadratic error functions again converted into the parameter for parameter and outputting the minimization parameter as motion between the images.